Одной из наиболее общих математических абстракций является понятие алгебраической системы < А, О, R >, где
Если операций нет - модель (структура). Если отношений нет - универсальная алгебра.
Математическая структура S=(M1,…,Mk; p1,…,ps) есть одно или несколько множеств М1,…,Мк, элементы которых находятся в некоторых отношениях р1,…,ps.
Структура данных - модель данных в виде математической структуры.
Примеры:
Значения представлены в виде объектов классов, являющихся производными из одного общего базового класса.
В поле значения звена списка размещается указатель на объект значение.
Для повышения общности схемы реализации будем использовать вместо величины NULL константу pStop для фиксации ситуаций, в которых указатель не содержит адрес какого-либо звена списка.
Информационные методы:
Методы доступа к значениям в списке:
Методы навигации по списку (итератор):
Вставка звеньев:
Удаление звеньев:
Схема стуктуры - структура данных Sa = (Ма, R; pa, p1), соответствующая рассмотрению структуры как переменной величины.
Алгоритм соответствует схеме структуры
Экземпляр - структура данных Sa ^ * = (Ма, R; pa, p1 ^ *) с установленными значениями элементов.
Вычисление соответствует экземпляру
Структуры с бинарными отношениями допускают случай графического изображения
Плекс - структура представления для выражений самого общего вида (линия – операция, точки – операнды)
Пример:
Структуры данных являются операндами операций обработки.
Результаты вычислений также являются структурами, модель которых может как совпадать, так и отличаться от структуры исходных данных.
Анализ примера:
Динамическая структура - математическая структура, которой соответствует частично-упорядоченное (по включению) базовое множество M, элементы которого являются структурами данных. При этом отношения включения индуцируются операциями преобразования структуры данных.
Примеры:
Средства поддержки динамической структуры - программы реализующие отношения включения
Динамические структуры данных – это структуры данных, память под которые выделяется и освобождается по мере необходимости.
Свойства:
Выгодно использовать, если:
Может быть эта схема здесь не нужна
Для имитации звеньев могут быть использованы два массива один из которых используется для хранения значений, другой- для хранения индексов следующих элементов. В этом случае, звено есть элемент массивов с одинаковым индексом, адрес (имя) звена – индекс массивов.
С использованием ООП звено может быть представлено в виде объекта. Образ памяти, выделенной для хранения структур данных, в это случае будет представлять массив звеньев-объектов.
Class TLink
{
Public:
Intvalue;//значение
Intnext;//индекс следующего звена
Protected:
TLink();
};
TLinkMem[MemLimit];
Множество – набор элементов
int TBitField::GetBit(const int n) const
{
if ((n > -1) && (n < BitLen))
return (pMem[(GetMemIndex(n))] & (GetMemMask(n)));
else return(0);
}
void TBitField::SetBit(const int n)
{ if ((n > -1) && (n < BitLen))
pMem[(GetMemIndex(n))] |= GetMemMask(n);
}
void TBitField::ClrBit(const int n)
{ if ((n > -1) && (n < BitLen))
pMem[(GetMemIndex(n))] &= ~GetMemMask(n);
}
TBitField TBitField::operator|(const TBitField& bf)
{
int i, len;
if (BitLen > bf.BitLen)
len = BitLen;
else len = bf.BitLen;
TBitField temp(len);
for (i = 0; i < MemLen; i++)
temp.pMem[i] = pMem[i];
for (i = 0; i < bf.MemLen; i++)
temp.pMem[i] |= bf.pMem[i];
return temp;
}
TBitField TBitField::operator&(const TBitField &bf)
{
int i, len;
if (BitLen < bf.BitLen)
len = BitLen;
else len = bf.BitLen;
TBitField temp(len);
for (i = 0; i < MemLen; i++)
temp.pMem[i] = pMem[i];
for (i = 0; i < bf.MemLen; i++)
temp.pMem[i] &= bf.pMem[i];
return temp;
}
TBitField TBitField::operator~(void)
{
TBitField temp(BitLen);
for (int i = 0; i < MemLen; i++)
temp.pMem[i] = ~pMem[i];
return temp;
}
Универс U – множество всех элементов.
Конкретизация (допущения и ограничения):
Битовое поле представляет из себя массив int
Бред, который нужно исправить:
Бред, который нужно исправить:
Структура хранения данного типа (звенья, сцепление, барьер, переменная связи) называется линейным или односвязным списком.
Среда выполнения обеспечивает динамически–распределяемую область памяти:
Базисное множество - структуры
Неоднозначность операций в том что можем вставлять как в голову так и в хвост и после текущего и удалять можно тоже по-разному.
Для показа неоднозначности взять простой односвязный линейный список с головой и двусвязный с хвостом и головой.
Множество – набор элементов. Для множества определены операции: проверка наличия элемента aA, добавление элемента A+a, удаление элемента A –a. Теоретико-множественные операции: объединение AB, пересечение AB, вычитание A. Универс U – множество всех элементов. Конкретизация (допущения и ограничения): элементы множества проиндексированы (каждому элементу соответствует уникальный индекс), множество индексов элементов составляют непрерывный диапазон целых значений. Тогда любое множество AU может быть описано характеристическим вектором =(1 2… n), , если иначе. Множество → битовая строка → массив битовых элементов → оперативная память (обратный порядок хранения). Нумерация бит в битовой строке – слева направо. Нумерация элементов в массиве – слева направо, биты элемента – справа налево. Байты двухбайтового элемента располагаются в ОП в обратном порядке (сначала байт с младшими битами, затем байт со старшими битами).
PTDatLink pTemp;
pTemp = new TDatLink();
pTemp-> SetDatValue(Val);
pTemp->SetNextLink(pFirst);
pFirst = pTemp;
PTDatLink pTemp = pFirst;
Val = pFirst->GetDatValue();
pFirst = pFirst->GetNextLink();
delete pTemp;
Перепаковка памяти (перепаковка) - процедура динамического перераспределения памяти путем переписи части хранимых значений в другую область
Перепаковка обеспечивает эффективное использование одного ресурса ЭВМ (памяти) за счет другого ресурса (времени).
Для выполнения перепаковки требуется разработка управляющих программ.
Управление памятью - выполнение функций анализа свободной памяти, планирование размещения структур, переписывание структур
Система управления памятью - комплекс программ, реализующих управление памятью
Необходимость перепаковки обуславливается принятым способом реализации отношений следования.
Свойства:
Выполняется при попытке вставки нового значения в стек s, у которого отсутствует свободная память: F = 'сумма' (Hik-Lik-1-1), 1 <= k <= N.
Для гарантированного выделения свободной памяти стеку s при наличии только одного свободного элемента памяти (случай 2), выполним:
Для хранения элементов можно выделить непрерывный вектор памяти размера 3n-2 Адрес (aij) = a(альфа) + 3(i-1) + (j-i)
Подход 1:
Подход 2:
Подход 3:
Подход 4:
Бред, который нужно исправить
это же треугольные матрицы, в матрице рамером n * n n ^ 2 ячееки, нулевые мы не храним
поиск будет О(1)т.к. мы просто индекс считаем грубо говоря,если с матрицами типо A + B,где а и б матрицы, то нам нужно каждый элемент с каждым сложитьсоотв. это будет такой же O как и у памятивычитание аналогично а как скалярное произведение матриц-сумма попарных произведений?
Статическое распределение памяти - распределение памяти до начала процесса вычислений.
Динамическое распределение памяти - распределение памяти в ходе выполнения программы.
Перепаковка памяти (перепаковка) - процедура динамического перераспределения памяти путем переписи части хранимых значений в другую область памяти.
Гипотезы о поведении структур служат основой для принятия решений о распределении памяти.
Формирование гипотез происходит в результате теоретического анализа модели решаемой задачи или может быть выполнено на основе статистических данных, получаемых в ходе вычислительных экспериментов с проектируемой программной системой.
Гипотеза 1: Стеки используются с одинаковой интенсивностью, память разделяется между стеками поровну.
Гипотеза 2: Интенсивность использования стеков различается.
Сохранение локальных тенденций роста:
правило распределение памяти для стеков в соответствии с их показателями роста
Li'k = Li'k-1 + (Hik-1 - Lik-1 + 1) + F * ((дельта, похожая на б итая) / (дельта в виде треугольника)), 1 < k < N
Гипотеза 3: Использование вероятностных предположений о поведении стеков.
Li'k = Li'k-1 + (Hik-1 - Lik-1 + 1) + (1-тета) * (F / N) + тета * F * ((дельта, похожая на б итая) / (дельта в виде треугольника)), 1 < k < N.
Множество – набор элементов
int TBitField::GetBit(const int n) const
{
if ((n > -1) && (n < BitLen))
return (pMem[(GetMemIndex(n))] & (GetMemMask(n)));
else return(0);
}
void TBitField::SetBit(const int n)
{ if ((n > -1) && (n < BitLen))
pMem[(GetMemIndex(n))] |= GetMemMask(n);
}
void TBitField::ClrBit(const int n)
{ if ((n > -1) && (n < BitLen))
pMem[(GetMemIndex(n))] &= ~GetMemMask(n);
}
TBitField TBitField::operator|(const TBitField& bf)
{ int i, len;
if (BitLen > bf.BitLen)
len = BitLen;
else len = bf.BitLen;
TBitField temp(len);
for (i = 0; i < MemLen; i++)
temp.pMem[i] = pMem[i];
for (i = 0; i < bf.MemLen; i++)
temp.pMem[i] |= bf.pMem[i];
return temp;
}
TBitField TBitField::operator&(const TBitField& bf)
{
int i, len;
if (BitLen < bf.BitLen)
len = BitLen;
else len = bf.BitLen;
TBitField temp(len);
for (i = 0; i < MemLen; i++)
temp.pMem[i] = pMem[i];
for (i = 0; i < bf.MemLen; i++)
temp.pMem[i] &= bf.pMem[i];
return temp;
}
TBitField TBitField::operator~(void)
{ TBitField temp(BitLen);
for (int i = 0; i < MemLen; i++)
temp.pMem[i] = ~pMem[i];
return temp;
}
Универс U – множество всех элементов
Способ задания отношения следования, в котором фиксация месторасположения следующего элемента производится путем запоминания соответствующего адреса памяти, называется сцеплением (пары, хранящие ai и ai+1, сцеплены адресными указателями). Для изображения структуры хранения с использованием сцепления звенья памяти рисуются в виде прямоугольников, а сцепление звеньев показывается в виде стрелок. Индикация последнего звена в списке обычно производится записью в поле адреса некоторого барьера – фиктивного (неадресного) значения (как правило, 0 или -1). Для доступа к звеньям списка должен быть известен адрес первого звена списка. Указатель, в котором этот адрес запоминается, называется переменной связи. Структура хранения данного типа (звенья, сцепление, барьер, переменная связи) называется линейным или односвязным списком.
Основные алгоритмические моменты метода сложения полиномов operator+ состоят в следующем:
TList TList::plus(TList list)
{
pLink tmp, ptr, temp, prev1, prev2, cnt, n;
tmp = prev1 = cnt = Head;
ptr = prev2 = temp = n = list.Head;
size = this->GetSize();
int flag = 1;
while ((tmp->pNext->data != -1) && (ptr->pNext->data != -1))
{
if ((ptr->data == -1) && (tmp->data == -1))
{
ptr = ptr->pNext;
tmp = tmp->pNext;
temp = temp->pNext;
cnt = cnt->pNext;
}
if ((tmp->data > ptr->data) && (flag == 1))
{
ptr = ptr->pNext;
this->insCurrent(temp->data, temp->data2);
list.deleteCurrent(temp->data);
temp = ptr;
flag = 0;
}
if ((tmp->data < ptr->data) && (flag == 1))
{
ptr = ptr->pNext;
tmp = tmp->pNext;
this->insCurrent(temp->data, temp->data2);
list.deleteCurrent(temp->data);
temp = ptr;
flag = 0;
}
if ((tmp->data == ptr->data) && (flag == 1))
{
this->insCurrent(tmp->data, tmp->data2 + ptr->data2);
if ((tmp->data2 + ptr->data2) == 0)
{
while ((prev1->pNext != tmp) && (n->pNext != ptr))
{
prev1 = prev1->pNext;
n = n->pNext;
}
tmp = tmp->pNext;
ptr = ptr->pNext;
this->deleteCurrent(cnt->data);
list.deleteCurrent(temp->data);
cnt = tmp;
temp = ptr;
}
flag = 0;
}
flag = 1;
}
if ((ptr->data == tmp->data) && (ptr->data != -1) && (tmp->data != -1))
{
this->insCurrent(ptr->data, tmp->data2 + ptr->data2);
if ((tmp->data2 + ptr->data2) == 0)
{
while ((prev1->pNext != tmp) && (n->pNext != ptr))
{
prev1 = prev1->pNext;
n = n->pNext;
}
tmp = tmp->pNext;
ptr = ptr->pNext;
this->deleteCurrent(cnt->data);
list.deleteCurrent(temp->data);
list.size--;
cnt = tmp;
temp = ptr;
}
}
if (ptr->data != tmp->data)
{
if (tmp->data == -1)
while (ptr->pNext != list.Head)
{
this->insCurrent(ptr->data, ptr->data2);
ptr = ptr->pNext;
list.size--;
}
}
if ((ptr->data != -1) && (tmp->data != -1))
{
this->insCurrent(ptr->data, ptr->data2);
list.deleteCurrent(ptr->data);
}
return *this;
}
В стандарте языка С++ предусматривается наличие в среде программирования стандартной библиотеки шаблонов (Standard Template Library, STL).
Основные понятия библиотеки STL.
Библиотека включает в свой состав большое количество контейнеров, представляющих собой структуры данных, в которых могут храниться объекты.
В числе имеющихся контейнеров:
vector<T> - вектор переменного размераlist<T> - двусвязный списокqueue<T> - очередьstack<T> - стекdeque<T> - декpriority_queue<T> - приоритетная очередьset<T> - множествоmultiset<T> - множество с повторением элементовmap<key,val> - ассоциативный массив (таблица)multimap<key,val> - ассоциативный массив с повторением ключейДля быстрого и эффективного построения вычислительных процедур, библиотека обеспечивает итераторы для всех видов контейнеров, которые представляют унифицированный механизм последовательного доступа к элементам контейнеров.
Общая схема:
<класс-контейнер>::iterator Iter; - объявление итератораIter = <объект-контейнер>.begin(); - установка на первый элементIter != <объект-контейнер>.end(); - проверка на завершение++Iter – переход к следующему элементуВ зависимости от типа контейнера, итератор может обеспечивать прямой доступ, быть одно- или дву- направленным, предназначенным только для чтения или записи и др. Библиотека содержит для контейнеров большое количество реализованных обобщенных алгоритмов.
В числе таких алгоритмов:
for_each() - вызвать функцию для каждого элемента,find() - найти первое вхождение элементаfind_if() - найти первое соответствие условиюcount()- подсчитать число вхождений элементаcount_if() - подсчитать число соответствий условиюreplace() - заменить элемент новым значениемcopy() - скопировать элементыunique_copy() - скопировать только различные элементыsort() - отсортировать элементыmerge() - объединить отсортированные последовательности и дрПечать текста: схема обхода
while (1)
{
if ( pLink != NULL )
{
cout << pLink->Str; // обработка звена
St.push(pLink); // запись в стек
pLink = pLink->pDown; // переход на подуровень
}
else if ( St.empty() )
break;
else
{
pLink = St.top();
St.pop(); // выборка из стека
pLink = pLink->pNext; // переход по тому же уровню
}
}
Ввод текста из файла: уровень текста в файле можно выделить строками специального вида (например, скобками '{' и '}').
Общая схема алгоритма:
повторить:
ввод строки
ЕСЛИ '}' ТО Завершить
ЕСЛИ '{' ТО Выполнить рекурсивно Ввод_текста
Добавить строку на том же уровне
Для копирования текста необходимо предварительно скопировать разделы текста, на которые указывают указатели pDown и pNext
Алгоритмы обхода NDT или DNT.
Каждое звено текста копируется за два прохода:
pDown (подуровень уже скопирован)Str значения Copy (для распознания звена при попадании на него при втором проходе)pNext указателя на звено-оригинал (для возможности последующего копирования текста исходной строки)Str и pNextПри удалении разделов текста для освобождения звеньев следует учитывать следующие моменты:
Память, занимаемая удаляемым текстом, не освобождается, а удаление текста фиксируется установкой указателей в состояние NULL (например, pFirst=NULL).
Возможный подход доступа к системе управления памятью – разработка специальной системы управления при помощи перегрузки операторов new и delete.
TTextLink создается статическая переменная MemHeader типа TTextMem.class TTextMem{
PTTextLink pFirst; // первое звено
PTTextLink pLast; // последнее звено
PTTextLink pFree; // первое свободное
InitMemSystem класса TTextLink.void TTextLink::InitMemSystem(int size) // инициализация памяти
{
char Line[100];
char *tmp = new char[sizeof(TTextLink)*size];
MemHeader.pFirst = (PTTextLink)new char[sizeof(TTextLink)*size];
MemHeader.pFree = MemHeader.pFirst;
MemHeader.pLast = (PTTextLink)tmp + size - 1;
PTTextLink pLink = MemHeader.pFirst;
for (int i = 0; i < size - 1; i++, pLink++) // размер памяти
pLink->pNext = pLink + 1;
pLink->pNext = nullptr;
}
void * TTextLink::operator new(size_t size) // выделение звена
{
PTTextLink pLink = MemHeader.pFree;
if (MemHeader.pFree != nullptr)
MemHeader.pFree = pLink->pNext;
return pLink;
}
delete звено включается в список свободных звеньев.void operator delete (void *pM)
{
PTTTextLink pLink=(PTTTextLink)pM;
pLink->pNext=MemHeader.pFree;
MemHeader.pFree=pLink;
}
Тmin=1
Tmax=log2N(при сбалансированном дереве)
Tmax=N(при вырожденном дереве)
Текст – линейная последовательность символов
Текст – линейная последовательность слов (слово - линейная последовательность символов)
Текст – линейная последовательность строк, строки состоят из слов, слова – из символов и т.д.
Математическая модель текста – иерархическая структура представления (дерево).
Единый тип звена:
typedef Tlink *PTLink;
class TLink
{
PTLink pNext;
int Atom; // =1 – звено-атом
union {PTLink pDown; char Symb;}
Таблица с вычисляемым входом (хеш-таблица) – это таблица, элементы которой располагаются в соответствии с некоторой функцией расстановки (хеш-функцией)
Функция расстановки f (ключ) вычисляет для каждого элемента таблицы по его ключу номер (позицию) элемента в массиве.
0…N–1 или 1…NМетод цепочек.
Замечания к открытому перемешиванию как способу размешения коллизий:
Широко используемый подход для разрешения коллизий - метод цепочек, когда все записи, для которых функция хеширования определяет одно и тоже значение,представляются в виде линейного списка.
Открытое перемешивание еще называют закрытым хэшированием, метод цепочек - открытое хэширование.
Печать текста: схема обхода
while (1)
{
if ( pLink != NULL )
{
cout << pLink->Str; // обработка звена
St.push(pLink); // запись в стек
pLink = pLink->pDown; // переход на подуровень
}
else if ( St.empty() )
break;
else
{
pLink = St.top();
St.pop(); // выборка из стека
pLink = pLink->pNext; // переход по тому же уровню
}
}
Ввод текста из файла: уровень текста в файле можно выделить строками специального вида (например, скобками '{' и '}')
Общая схема алгоритма:
повторить:
ввод строки
ЕСЛИ '}' ТО Завершить
ЕСЛИ '{' ТО Выполнить рекурсивно Ввод_текста
Добавить строку на том же уровне
Реализация итератор:
int TText::Reset(void) // Установка на корневое звено текста
{
pCurrent = pFirst;
if (pCurrent != nullptr)
{
St.push(pCurrent);
if (pCurrent->pNext != nullptr)
St.push(pCurrent->pNext);
if (pCurrent->pDown != nullptr)
St.push(pCurrent->pDown);
}
}
bool TText::IsTextEnded(void) const // Стек пуст?
{
return St.empty();
}
bool TText::GoNext(void) // Переход к следующему звену текста
{
if (!IsTextEnded())
{
pCurrent = St.top();
St.pop();
if (pCurrent != pFirst)
{
if (pCurrent->pNext != nullptr)
St.push(pCurrent->pNext);
if (pCurrent->pDown != nullptr)
St.push(pCurrent->pDown);
}
}
return IsTextEnded();
}
Формат записи выражения.
'=': A+(B-C)*D-F/(G+H)=.Алгоритм:
'*' '/' (3), '+' '-' (2), '(' (1), '=' (0),void TText::DelDownLine(void) // Удаление строки в подуровне
{
if (pCurrent == nullptr)
SetRetCode(TextErr);
else if (pCurrent->pDown == nullptr)
SetRetCode(TextNoDown);
else if (pCurrent->pDown->IsAtom())
pCurrent->pDown = pCurrent->pDown->pNext;
}
void TText::InsDownLine(string str) // Вставка строки в подуровень
{
if (pCurrent == nullptr)
SetRetCode(TextErr);
else
{
TStr buf; // typedef char TStr[TextLineLength];
strcpy(buf, str.c_str());
pCurrent->pDown = new TTextLink(buf, pCurrent->pDown, nullptr);
}
}
void TTreeTable :: DelRecord ( TKey k ) { // удалить запись
if ( FindRecord(k) == NULL ) SetRetCode(TabNoRec); // SKIP_ON
else {
SetRetCode(TabOK);
PTTreeNode pNode = *ppRef;
if ( pNode->pRight == NULL ) *ppRef = pNode->pLeft; // один потомок слева
else if ( pNode->pLeft == NULL ) *ppRef = pNode->pRight; // один потомок справа
else { // два потомка - поиск крайнего справа у левого поддерева
PTTreeNode pN = pNode->pLeft, *ppR = &pNode->pLeft;
while ( pN->pRight != NULL ) {
ppR = &pN->pRight; pN = *ppR;
} // вместо удаления pNode удается pN
pNode->pValue = pN->pValue; // значение в pNode
pNode->Key = pN->Key;
pNode = pN; *ppR = pN->pLeft; // обход удаляемого pN
}
delete pNode;
} // SKIP_OFF
}
Дерево является идеально сбалансированным если для каждого его узла количество узлов в левом и правом поддеревьях различаются не более чем на 1. Дерево является сбалансированным,если для каждого узла высота левого и правого поддеревьев различаются не более,чем на 1(АВЛ-деревья). Идеально сбалансированные деревья являются сбалансированными.Операции обработки сбалансированных деревьев имеют сложность log2N.(поиск,вставка,удаление) Тmin=1 Tmax=log2N(при сбалансированном дереве) Tmax=N(при вырожденном дереве)
Структура памяти
Структура данных
К - множество именА - множество адресовf:К->АВозможные задания f:возможный способ-табличное задание функции:
Операции под таблицей:
Таблица - динамическая структура данных.
Базисное множество - семейство линейных структур из записей, базисное отношение включения определяется операциями вставки и удаления записей.
Варианты расширения понятия таблицы:
Принцип реализации таблиц:
Введение различных способов предполагает явное или неявное существование разных типов ситуаций при использовании таблиц.
Просматриваемые таблицы.
Таблица последовательности строк(записей)
По организации способа доступа таблицы делятся на следующие категории:
В просматриваемой таблице порядок расположения элементов никак не связан со значениями ключей (рис. II-34). Поэтому поиск элемента по ключу осуществляется обычным просмотром всех элементов таблицы, начиная с первого и до искомого
| Ключ | Информация |
|---|---|
| 08 | ... |
| 33 | ... |
| 47 | ... |
| 25 | ... |
| 18 | ... |
рис. II-34
Таким образом, при удалении элемента надо:
Поскольку операция поиска возвращает искомый элемент и не сообщает о месте его размещения в списке, при реализации операции удаления элемента из списка приходится либо
Алгоритм удаления элемента из просматриваемой таблицы-списка по варианту a) приведен на рис. II–39.
Ниже приводится текст программы, соответствующий приведенному алгоритму.
struct Item
{
int key;
Type info;
Item *next;
};
Item *ptab; /*указатель на начало таблицы */
int del1(int k)
{
Item *cur, *prev;
cur = ptab;
/*проверяем, есть ли в таблице элементы */
if(!cur)
return -1; /*таблица пуста – отказ */
/*возможно, требуется удалить первый элемент таблицы */
if(cur->key == k)
{
/* удаляем первый элемент */
ptab = cur->next;
delInfo(cur->info);
delete cur;
return 0;
}
/* ищем удаляемый элемент среди других элементов таблицы */
while(cur->next)
{
/* есть другие элементы */
prev = cur;
cur = cur->next;
if(cur->key == k)
{
/* нашли элемент, который надо удалить */
prev->next = cur->next;
delInfo(cur->info);
delete cur;
return 0;
}
}
/* естественный выход из цикла – в таблице нет элемента с ключом k */
return -1;
}
Дерево является идеально сбалансированным если для каждого его узла количество узлов в левом и правом поддеревьях различаются не более чем на 1. Дерево является сбалансированным,если для каждого узла высота левого и правого поддеревьев различаются не более,чем на 1(АВЛ-деревья). Идеально сбалансированные деревья являются сбалансированными.Операции обработки сбалансированных деревьев имеют сложность log2N.(поиск,вставка,удаление) Тmin=1 Tmax=log2N(при сбалансированном дереве) Tmax=N(при вырожденном дереве)
Сортированные (упорядоченные) таблицы - таблицы, в которых записи располагаются в порядке возрастания (или убывания) ключей
Упорядоченность таблиц может быть организована только при возможности сравнения ключей (на множестве ключей задано отношение линейного порядка).
Сортировка - действия, связанные с размещением записей в порядке возрастания (или убывания) ключей
Алгоритм сортировки называют устойчивым, если он никогда не меняет относительный порядок в таблице двух записей с равными ключами
Внутренняя сортировка - Упорядочивание данных, при котором все значения располагаются в ОП
Сортировка включением
Идея похода – вставка нового значения в упорядоченный набор данных.
Алгоритм быстрой сортировки.
Идея подхода (Hoare C.A.R.)– использование процедуры разделения упорядочиваемого набора на две части, в одной из которых располагаются значения, меньшие некоторого порогового (ведущего) элемента массива, в другой – соответственно большие значения. Подобный способ разделения может быть выполнен без привлечения дополнительной памяти.
При наличии процедуры разделения алгоритм сортировки может быть определен рекурсивно – необходимо разбить упорядочиваемый набор на два блока с меньшими и большими значениями соответственно и затем последовательно отсортировать полученные блоки.
Все свободные звенья объединяются в один список свободных звеньев. Звенья этого списка используются при необходимости свободной памяти, в этот список звенья должны возвращаться после освобождения.
Схемы работы со стеком и со списком свободных звеньев совпадают. Список свободных звеньев есть стек.
Дерево - связный граф без циклов
Структура типа дерева (древовидная структура) с базовым типом T
Дерево поиска - деревоб в котором для любой вершины бинарного дерева значения в левом потомке меньше значения узла, а значение в правом потомке больше значения узла
Обработка дерева – выполнение необходимой операции для каждой узла дерева. Реализация подобного типа действий предполагает умение обхода (обхода) дерева
| Непрерывная память | Списки |
|---|---|
| Перепаковка для динамического распределения памяти | Динамическое распределение памяти эффективно реализуется при помощи списка свободных звеньев |
| В структуре хранения хранятся только данные | В структуре хранения хранятся данные и указатели |
| К элементам структуры данных обеспечивается | К элементам структуры данных обеспечивается |
| Прямой доступ | Последовательный доступ |
Рассмотрим в качестве базовых объектов основные геометрические фигуры – точку, окружность, прямоугольник и т.д.
Информационное описание объектов – параметры фигуры (координаты, размер, радиус и др.). В общем случае, описание фигуры включает значение координат некоторой опорной точки.
Операции обработки геометрических объектов включают методы для задания и изменения параметров; расширим набор операций процедурами визуализации (например, на экране дисплея) и скрытия фигур.
Для обеспечения возможности динамической визуализации геометрических объектов введем тип данных, значения которого вычисляются в соответствии с задаваемым формульным выражением.
Составной объект – набор геометрических объектов (как базовых, так и составных), рассматриваемых при выполнении операций обработки как единый объект.
Геометрический объект может быть сконструирован с использованием уже существующих объектов (например, ломаная может быть определена через набор конечных точек составляющих отрезков).
Геометрический объект может быть образован при помощи сборки существующих объектов – рассмотрим данный способ построения новых объектов на примере рисунков (чертежей), образованных только из объектов двух базовых типов: точек и линий
#define MemSize 25 // размер памяти для стека
class TStack
{
protected:
int Mem[MemSize]; // память для СД
int Top; // индекс последней занятой ячейки
public:
TStack () { Top = -1; }
int IsEmpty (void) const { Top == -1; }
int IsFull (void) const { Top == MemSize-1;}
void Put ( const int Val ) { Mem[++Top] = val; }
TData Get (void) { return Mem[Top--]; }
};
Способы достижения полного использования памяти:
Сдвиг значений очереди после выборки очередного значения (т.е. обеспечение Li=0) – возрастание накладных расходов, использование левого участка свободной области при достижении Hi=n-1 (т.е. при отсутствии свободной памяти справа).
Циклический или кольцевой буфер - структура хранения, получаемая из вектора расширением отношения следования парой p(an,a1). Реализация кольцевого буфера логически может быть обеспечена переходом индексов Li и Hi при достижении граничного значения MemSize-1 на индекс первого элемента вектора памяти.
Агрегация – это абстракция, которая превращает связь между объектами в некоторый агрегированный объект.
Составной объект - набор геометрических объектов (как базовых так и составных), рассматриваемых при выполнении операций обработки как единый объект
class TChartGroup : public TChartRoot
{
protected:
TDatList Group; // Список объектов
public:
TChartGroup() { }
void InsUnit(TChartRoot *pUnit); // Добавление
virtual void Show(); // Визуализация
virtual void Hide(); // Скрытие
virtual void CalcParams(double t = -1); // Пересчет параметров
};
Геометрический объект может быть сконструирован с использованием уже существующих объектов
class TChartPolyline : public TChartGroup
{
public:
TChartPolyline() { }
void InsPoint(TChartRoot *pUnit); // Добавление
virtual void Show(); // Визуализация
virtual void Hide(); // Скрытие
virtual void CalcParams(double t = -1); // Пересчет параметров
};
Агрегация – это абстракция, которая превращает связь между объектами в некоторый агрегированный объект.
Составной объект - набор геометрических объектов (как базовых так и составных), рассматриваемых при выполнении операций обработки как единый объект
class TChartGroup : public TChartRoot
{
protected:
TDatList Group; // Список объектов
public:
TChartGroup() { }
void InsUnit(TChartRoot *pUnit); // Добавление
virtual void Show(); // Визуализация
virtual void Hide(); // Скрытие
virtual void CalcParams(double t = -1); // Пересчет параметров
};
Геометрический объект может быть сконструирован с использованием уже существующих объектов
class TChartPolyline : public TChartGroup
{
public:
TChartPolyline() { }
void InsPoint(TChartRoot *pUnit); // Добавление
virtual void Show(); // Визуализация
virtual void Hide(); // Скрытие
virtual void CalcParams(double t = -1); // Пересчет параметров
};
FindRecord(TKey k, PTTreeNode pNode)
{
if (pNode != NULL)
{ // лист
if (pNode->Key < k) // вправо
pNode = FindRecord(k, pNode->Right);
if (pNode->Key > k) // влево
pNode = FindRecord(k, pNode->Left);
}
return pNode;
}
Введение барьера.
FindRecord(TKey k, PTTreeNode pNode)
{
if (pNode->Key < k) // вправо
pNode = FindRecord(k, pNode->Right);
if (pNode->Key > k) // влево
pNode = FindRecord(k, pNode->Left);
return (pNode == pBarrier) ? NULL : pNode;
}
void TTreeTable ::InsRecord(TKey k, PTDatValue pVal)
{ // вставить запись
if (IsFull())
SetRetCode(TabFull);
else if (FindRecord(k) != NULL)
SetRetCode(TabRecDbl);
else
{
SetRetCode(TabOK);
\*ppRef = new TTreeNode(k, pVal);
DataCount++;
}
}
while (pN (не принадлежит) TChartPoint)
{
St.push(pN);
pN = pN->GetFirstPoint();
}
//подъем по плексу и рисование
pF = pN;
while (!St.Empty())
{
pN = St.top();
St.Pop();
pL = pN->GetLastPoint(); //рисование линии<pN, pF, pL>
pF = pL;
}
TChartPoint *Show(TChart *pN)
{
if (pN != NULL)
pL = NULL;
else if (pN (принадлежит) TChartPoint)
pL = pN;
else
{
pF = Show(pN->GetFirstPoint());
pL = Show(pN->GetLastPoint()); //рисование линии <pN,pF,pL>
}
return pN;
}
Линейные структуры данных - структуры, которым соответствует ориентированный граф с вершинами, лежащими на одной ломаной
Линейные структуры данных - упорядоченные структуры, в которых адрес элемента однозначно определяется его номером
Свойства:
Примеры линейных структур:
Таблица – динамическая структура данных, базисным множеством которой является семейство линейных структур из записей.
Запись – кортеж, каждый элемент которого обычно именуется полем.
Имя записи (ключ) – одно из полей записи, по которому обычно осуществляется поиск записей в таблице; остальные поля образуют тело записи.
Хеш-функция – функция, ставящая в соответствие ключу номер записи в таблице.
Хеш-таблицами, таблицами с вычисляемыми адресами или перемешиваемыми таблицами называют таблицы, получаемые при некотором способе построения.
h(key), которая отображает множество имен на множество номеров строк таблицыПри использовании таблиц с вычисляемыми адресами может возникнуть ряд дополнительных проблем
Так, например, при вставке новой записи функция расстановки может выдать номер занятой строки массива (функция расстановки может определять одни и те же значения для нескольких разных ключей)
Метод открытого перемешивания (или закрытое хеширование) состоит в добавлении к вычисленному занятому номеру некоторого фиксированного смещения (поторное перемешивание) k' = (k + p) mod N
k' также является занятым, следует повторить процедуру повторного перемешивания до тех пор, пока не обнаружится свободная строка, либо таблица не будет исчерпанаp и N являются взаимнопростыми, открытое перемешивание обеспечивает нахождение свободной строки массиваСреднее количество просматриваемых записей при поиске записи в перемешиваемых таблицах
Tср = (1 - a / 2) / (1 - a)
a - коэффициент заполненности таблицы (a = N / M)M - количество строк в массиве для хранения записейN - количество записей в таблице.Следует отметить, что количество сравнений при поиске в перемешиваемых таблицах зависит не от количества записей в таблице, а от заполненности памяти, отведённой для размещения записей. Для примера, при заполненности массива на 75% (a = 0.75) количество сравнений в среднем равно 2.5.
Функция преобразования значения ключа к номеру (адресу) строки памяти для хранения записи H: K → L (L = { 0, ... , M - 1 }) называется функцией расстановки (хеширования, перемешивания, рассеивания). Таблицы, представление которых организуется при использовании функции расстановки, называются таблицы с вычислимыми адресами (хеш-таблицы, перемешиваемые таблицы). При M < N (M - количество строк памяти, N - количество записей) функция расстановки является взаимно-неоднозначной (неинъективной). Темсымым, при использовании функции расстановки могут возникать ситуации, когда получаемый функцией номер строки памяти для расположения записи уже является использованным. Ситуация, когда для расположения записи функцией расстановки определяется уже занятая строка памяти, называется относительным переполнением (коллизией). Уменьшение эффекта сгущений может быть достигнуто при применении способа открытого или линейного перемешивания s' = (s + p) mod M (1 <= p < M). Возможное решение нахождения свободных строк состоит в выборе взаимнопростых значений для M и p. В более общем виде правило разрешения коллизии может быть представлено как функция вторичного перемешивания s' = h'(s).
Теорема: Алгоритм открытого перемешивания при взаимно-простых M и p гарантирует нахождение свободных строк структуры хранения таблицы.
Доказательство: Рассмотрим множество G = { 0, 1, ... , M - 1 } с операцией a ⊕ b = (a + b) mod M. Свойства операции: G замкнута относительно ⊕, операция ассоциативна и коммутативна, ∃ нулевой и обратные элементы => Множество G с операцией ⊕ является группой. Выделим подмножество G' = { 0, a, a ⊕ a, ... }. Такое множество G' с операцией ⊕ тоже является группой (такие группы называются циклическими). Обозначим a ⊕ a ⊕ ... ⊕ a через na (a - число повторений). Если n > 0, то минимальное значение n, при котором na = 0, называется порядком элемента a и обозначатся |a| (т.е. порядок определяет количество итераций открытого перемешивания, после которого начнётся повторение строк). Целое значение в операции (n a) / M получится только при n = M (т.к. a < M и для взаимно простых a и M). Но это означает также, что na = 0, и, тем самым, |a| = M. Отсюда следует G = G'.
При открытом перемешивании размер памяти для таблицы фиксирован + хранение записей без упорядоченности по ключам.
При разрешении коллизии просматриваемые строки могут рассматриваться как список, в котором порядок следования определяется при помощи алгоритмического правила. Тем самым, удаление записи в середине подобного списка не должно разрушать связность записей. Это может быть достигнуто специальной маркировкой строк с удалёнными записями. Строка структуры хранения имеет три возможных состояния - свободное, занятое, пустое (пустое состояние строки возникает посе удаления хранимой в строке записи).
Вставка:
1. Если n==M, ТО { Переполнение; Останов }
2. f = -1 // f – номер первой найденной пустой строки
3. s = h(key) // применение функции расстановки
4. ЕСЛИ s занята и K[s]==key, ТО {Дублир.; Останов }
5. ЕСЛИ s пустая и (f < 0), ТО { f = s }
6. ЕСЛИ s свободна и (f < 0), ТО { K[s]=key; Останов }
7. ЕСЛИ s свободна и (f >-1), ТО { K[f]=key; Останов }
8. (!) Коллизия {s = (s+p) mod M и переход к п. 4 }.
Поиск:
1) f = -1 // f – номер первой найденной пустой строки
2) s = h(key) // применение функции расстановки
3) ЕСЛИ s занята и K[s]==key, ТО { Останов }
4) ЕСЛИ s пустая и (f < 0), ТО { f = s }
5) ЕСЛИ s свободна, ТО { Останов }
6) (!) Коллизия { s = (s+p) mod M и переход к п. 3 }.
Необходимость перепаковки для обеспечения динамического распределения памяти возникает в силу принятого способа реализации отношения следования - следующий элемент структуры располагается в следующем элементе памяти (с адресом, большим на 1). Устранение перепаковки возможно только при кардинальном изменении способа реализации основных отношений – необходимо допустить размещение следующих элементов структуры в произвольных элементах памяти (там, где имеется свободные области памяти). Возможность такого подхода может быть обеспечена запоминанием для каждого текущего элемента структуры адреса памяти, где хранится следующий элемент. Интерпретация содержимого элемента памяти (значение или адрес следующего элемента) в самом простом варианте может быть обеспечена фиксированным форматом используемых участков памяти.
Под квантом памяти понимается последовательность элементов памяти с последовательно-возрастающими адресами.
Именем (адресом) этой группы считается адрес первого слова кванта. Элементы кванта называются полями. В общем случае, набор элементов памяти, связанных с одним именем, называют звеном.
Далее будут использоваться двухэлементные звенья памяти, в которых первое поле будет использоваться для хранения значений, а второе поле – для запоминания адресов.
Способ задания отношения следования, в котором фиксация месторасположения следующего элемента производится путем запоминания соответствующего адреса памяти, называется сцеплением (пары, хранящие ai и ai+1, сцеплены адресными указателями).
Для изображения структуры хранения с использованием сцепления звенья памяти рисуются в виде прямоугольников, а сцепление звеньев показывается в виде стрелок.
Индикация последнего звена в списке обычно производится записью в поле адреса некоторого барьера – фиктивного (неадресного) значения (как правило, 0 или -1). Для доступа к звеньям списка должен быть известен адрес первого звена списка. Указатель, в котором этот адрес запоминается, называется переменной связи.
Структура хранения данного типа (звенья, сцепление, барьер, переменная связи) называется линейным или односвязным списком.
Таблица – динамическая структура данных, базисным множеством которой является семейство линейных структур из записей. Запись – кортеж, каждый элемент которого обычно именуется полем. Имя записи (ключ) – одно из полей записи, по которому обычно осуществляется поиск записей в таблице; остальные поля образуют тело записи. Хеш-функция – функция, ставящая в соответствие ключу номер записи в таблице.
Хеш-таблицами, таблицами с вычисляемыми адресами или перемешиваемыми таблицами называют таблицы, получаемые при некотором способе построения. Этот способ построения таблиц при большом количестве записей состоит в предварительном (перед непосредственным поиском по таблице) вычислении месторасположения искомой записи. Данный метод предполагает наличие некоторой простой функции h(key), которая отображает множество имен на множество номеров строк таблицы. Эта функция называется функцией хеширования или расстановки.
Эффективность обработки табиц с вычислимым входом зависит не от количества записей, а от степени заполненности структуры хранения.
При использовании таблиц с вычисляемыми адресами может возникнуть ряд дополнительных проблем. Так, например, при вставке новой записи функция расстановки может выдать номер занятой строки массива (функция расстановки может определять одни и те же значения для нескольких разных ключей). Такая ситуация называется относительным переполнением таблицы или коллизией. При возникновении коллизий возможны разные методы их разрешения. Рассмотрим метод цепочек.
Метод цепочек при возникновении коллизий формирует линейные списки (цепочки), в каждом из которых располагаются записи с одинаковым значением функции расстановки (в этом случае в строках массива для размещения записей следует добавить ещё одно поле для ссылки на следующее звено списка).
Функция преобразования значения ключа к номеру (адресу) строки памяти для хранения записи H: K → L (L = { 0, ... , M - 1 }) называется функцией расстановки (хеширования, перемешивания, рассеивания). Таблицы, представление которых организуется при использовании функции расстановки, называются таблицы с вычислимыми адресами (хеш-таблицы, перемешиваемые таблицы). При M < N (M - количество строк памяти, N - количество записей) функция расстановки является взаимно-неоднозначной (неинъективной). Темсымым, при использовании функции расстановки могут возникать ситуации, когда получаемый функцией номер строки памяти для расположения записи уже является использованным. Ситуация, когда для расположения записи функцией расстановки определяется уже занятая строка памяти, называется относительным переполнением (коллизией).
Метод цепочек (или открытое хеширование) - все записи, для которых функция хеширования определяет одно и тоже значение, представляются в виде линейного списка.
Метод цепочек обеспечивает получение структуры хранения таблицы с динамическим распределением памяти.
Каждая ячейка массива является указателем на связный список (цепочку) пар ключ-значение, соответствующих одному и тому же хеш-значению ключа. Коллизии просто приводят к тому, что появляются цепочки длиной более одного элемента. Операции поиска или удаления элемента требуют просмотра всех элементов соответствующей ему цепочки, чтобы найти в ней элемент с заданным ключом. Для добавления элемента нужно добавить элемент в конец или начало соответствующего списка, и, в случае, если коэффициент заполнения станет слишком велик, увеличить размер массива и перестроить таблицу.
Плекс может рассматриваться как структура представления для выражений самого общего вида (линия – операция, точки - операнды).
Пример: Арифметическое выражение (a * b + c) * (d - e / f):
НЕТУ ЧОТАМножество – набор элементов.
Для множества определены операции:
Проектирование:
При удалении разделов текста для освобождения звеньев следует учитывать следующие моменты:
Память, занимаемая удаляемым текстом, не освобождается, а удаление текста фиксируется установкой указателей в состояние NULL (например, pFirst=NULL). Подобный способ выполнения операций удаления текста может привести к ситуации, когда в памяти, используемой для хранения текста, могут присутствовать звенья, на которые нет ссылок в тексте и которые не возвращены в систему управления памятью для повторного использования. Элементы памяти такого вида носят наименование "мусора". Наличие "мусора" в системе может быть допустимым, если имеющейся свободой памяти достаточно для работы программ. В случае нехватки памяти необходимо выполнить "сборку мусора".
Возможный подход доступа к системе управления памятью – разработка специальной системы управления при помощи перегрузки операторов new и delete.
Общая схема подхода:
TTextLink создается статическая переменная MemHeader типа TTextMem.class TTextMem{
PTTextLink pFirst; // первое звено
PTTextLink pLast; // последнее звено
PTTextLink pFree; // первое свободное
InitMemSystem класса TTextLink.void TTextLink::InitMemSystem(int size) // инициализация памяти
{
char Line[100];
char *tmp = new char[sizeof(TTextLink)*size];
MemHeader.pFirst = (PTTextLink)new char[sizeof(TTextLink)*size];
MemHeader.pFree = MemHeader.pFirst;
MemHeader.pLast = (PTTextLink)tmp + size - 1;
PTTextLink pLink = MemHeader.pFirst;
for (int i = 0; i < size - 1; i++, pLink++) // размер памяти
pLink->pNext = pLink + 1;
pLink->pNext = nullptr;
}
void * TTextLink::operator new(size_t size) // выделение звена
{
PTTextLink pLink = MemHeader.pFree;
if (MemHeader.pFree != nullptr)
MemHeader.pFree = pLink->pNext;
return pLink;
}
delete звено включается в список свободных звеньев.void operator delete (void *pM)
{
PTTTextLink pLink=(PTTTextLink)pM;
pLink->pNext=MemHeader.pFree;
MemHeader.pFree=pLink;
}
Составной объект - набор геометрических объектов (как базовых так и составных), рассматриваемых при выполнении операций обработки как единый объект
class TChartGroup : public TChartRoot
{
protected:
TDatList Group; // Список объектов
public:
TChartGroup() { }
void InsUnit(TChartRoot *pUnit); // Добавление
virtual void Show(); // Визуализация
virtual void Hide(); // Скрытие
virtual void CalcParams(double t = -1); // Пересчет параметров
};
Геометрический объект может быть сконструирован с использованием уже существующих объектов
class TChartPolyline : public TChartGroup
{
public:
TChartPolyline() { }
void InsPoint(TChartRoot *pUnit); // Добавление
virtual void Show(); // Визуализация
virtual void Hide(); // Скрытие
virtual void CalcParams(double t = -1); // Пересчет параметров
};
Геометрический объект может быть образован при помощи сборки существующих объектов.
Рассмотрим данный способ построения новых объектов на примере рисунков (чертежей), образованных только их объектов двух базовых типов: точек и линий
while (pN (не принадлежит) TChartPoint)
{
St.push(pN);
pN = pN->GetFirstPoint();
}
//подъем по плексу и рисование
pF = pN;
while (!St.Empty())
{
pN = St.top();
St.Pop();
pL = pN->GetLastPoint(); //рисование линии<pN, pF, pL>
pF = pL;
}
TChartPoint *Show(TChart *pN)
{
if (pN != NULL)
pL = NULL;
else if (pN (принадлежит) TChartPoint)
pL = pN;
else
{
pF = Show(pN->GetFirstPoint());
pL = Show(pN->GetLastPoint()); //рисование линии <pN,pF,pL>
}
return pN;
}
ДОБАВИТЬ ПИКЧИ
Алгоритмы обхода (итератор)
TSearchMode; // способ обхода
PTGraphNode pCurrNode; // текущая вершина
// Достигнутые, но не обработанные вершины
TDataRoot *pStream;
// Множество вершин, достигнутых в ходе обхода
TBitField *pFound;
Инициализация (Reset)
pStream и ее отметка в множестве pFoundGoNextПроверка завершения (IsGraphEnded)
return pCurrNode == NULL // тукущее звено?
Переход к следующей вершине графа (GoNext)
pStreampStream int Reset (void); // установить на первую вершину
int IsGraphEnded (void) const; // обход завершен?
int GoNext (void); // переход к следующей вершине
PTGraphNode GetCurrNode (void) { return pCurrNode; } // доступ
PTGraphPath GetShortestPath (string fn, string ln); // поиск кратчайшего пути
protected:
virtual void Print (ostream &os); // печать графа
};
typedef TGraph * PTGraph;
// end of tgraph.h